#include<bits/stdc++.h>
#define int long long 
#define mk(a,b,c) make_pair(a,make_pair(b,c))
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>=10)write(x/10);
	putchar(x%10+'0');	
}
const int N=3e3+5;
int n,m;
int fa[N];
int b[N][N];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void sol(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			b[i][j]=(i>j?i-j:j-i);
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		b[x][y]=b[y][x]=z;	
	}
	priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>q;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			q.push(mk(b[i][j],i,j));
	int ans=0;
	while(!q.empty()){
		int dis=q.top().first,x=q.top().second.first,y=q.top().second.second;
		q.pop();
		int X=find(x),Y=find(y);
		if(X^Y){
			fa[X]=Y;
			ans+=dis;	
		}
	}
	write(ans),putchar('\n');
}
signed main(){
	freopen("up.in","r",stdin);
	freopen("up.out","w",stdout);
	int T=read();
	while(T--)sol();
	return 0;
}
